一道组合老题

huhuyang2010

此题是1991年BMO一道题，相当于现在自招难度。大家试试。

karen_jeff

有点难度的 .

huhuyang2010

给出答案：
记f(n,k)为1-n的排列中，(n1,n2,...ni)不是（1,...,i）的排列数目,其中1<=i<=k。
则f(n,k)=f(n,k-1)-f(k,k-1)*(n-k)! 。
这是因为f(n,k)对应的排列必然在f(n,k-1)的排列中，需要将f(n,k-1)排列集中去除掉不满足(n1,n2,...nk)不是（1,...,k）的排列，即将f(n,k-1)排列集中去除掉(n1,n2,...nk)是(1,...,k）的排列，满足这样条件的(n1,n2,...,nk)有f(k,k-1)个，所以应该去除掉f(k,k-1)*(n-k)! 个排列。
由此可得：
f(n,0)=n!
f(n,1)=f(n,0)-f(1,0)*(n-1)!=n!-(n-1)!
f(n,2)=f(n,1)-f(2,1)*(n-2)!=n!-(n-1)!-(n-2)!
f(n,3)=f(n,2)-f(3,2)*(n-3)!=n!-(n-1)!-(n-2)!-3(n-3)!
f(n,4)=f(n-3)-f(4,3)*(n-4)!=n!-(n-1)!-(n-2)!-3(n-3)!-13(n-4)!
f(n,5)=f(n,4)-f(5,4)*(n-5)!=n!-(n-1)!-(n-2)!-3(n-3)!-13(n-4)!-71(n-5)!
所以f(6,5)=461。

这道题用的是动态规划来解决。
递推其实是一种特殊的动态规划。